package com.sise.Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 *      227. 基本计算器 II
 *      给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 *      整数除法仅保留整数部分。
 *
 *      输入：s = " 3+5 / 2 "
 *      输出：5
 */
public class _227_calculate {

    // 13
    public static void main(String[] args) {
        int calculate = calculate(" 1 3 - 3 - 8 / 2 ");
        System.out.println(calculate);
    }

    static public int calculate(String s) {
        /**
         * 总体思路：
         *      创建一个栈，先进行数值遍历，获取到完整的数值，例如将 1 3 合成 13，将其存储到栈中，
         *      然后遍历到 运算符，如果是 加减号(13 - 3 - 8) ，那就更换符号为减号，接着遍历字符 3，
         *      直到遇见 第二个符号(- 8)，我们进入 case，那么存储的 -num 就是 -3，如果是乘除法，那么就取出栈顶元素进行计算后放回，
         *      等到全部遍历完成后，那么就把数据都拿出来 ans += stack.pop();
         */
        Deque<Integer> stack = new LinkedList<>();
        // 一开始将其设置为加号，存的时候就为 num，此时不需要加号(+num)，因为取出来的时候，ans += num
        char preSign = '+';
        // 一开始的 num 设置为 0，方便后续赋值
        int num = 0;
        int n = s.length();
        // 先将全部的数值都遍历一遍
        for (int i = 0; i < n; ++i) {
            // 判断是否为字符串，如果是的话，将其组合起来： 1 2 3 + 4 => 123 + 4
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            // 当遇见非字符时，也就是"+ - * /"，将其存入栈中
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        // 这里不像前面一样存进去，而是取出来，但这里的取出来的是 栈顶元素，例如取出的是 13 - 8 / 2 中的 8
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                }
                // preSign 代表符号，假设 1-22+3，那么我们是先遍历到 - 号，此时我们就将 preSign 设置为 - ，紧接着遍历 2、+ ，到了 + 号的时候，此时preSign为-，num为22，故此进入case中，-num为-22
                preSign = s.charAt(i);
                // 每次都会重置为0，方便下一组数字赋值： 123 + 3 3 1 中的 331 赋值
                num = 0;
            }
        }
        int ans = 0;
        // 此时栈内只有加号、减号。故此之间拿出来遍历相加即可
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }
}
